﻿using System;
using System.Collections;
using System.Collections.Generic;
using System.Runtime.CompilerServices;

namespace Nirvana
{
    public sealed class PriorityQueue<T> : IEnumerable<T>
    {
        private IComparer<T> comparer;
        private T[] queue;
        public int Count { get;  set; }
        public T this[int index]
        {
            get
            {
                return this.queue[index];
            }
        }

        public PriorityQueue() : this(null)
        {

        }

        public PriorityQueue(int capacity) : this(capacity, null)
        {
        }
        public PriorityQueue(IComparer<T> comparer) : this(16, comparer)
        {
        }

        public PriorityQueue(int capacity, IComparer<T> comparer)
        {
            if (comparer == null)
            {
                comparer = Comparer<T>.Default;
            }
            this.comparer = comparer;
            this.queue = new T[capacity];
        }

        public void Push(T v)
        {
            if(this.Count >= this.queue.Length)
            {
                Array.Resize<T>(ref this.queue,this.Count *2);
            }
            this.queue[this.Count] = v;
            Sort(this.Count++);
        }

        public T Pop()
        {
            T result = this.Top();
            this.queue[0] = this.queue[--Count];
            if (this.Count > 0) PopSort(0);
            return result;
        }

        public T Top()
        {
            if (this.Count > 0) return this.queue[0];
            throw new InvalidOperationException("The PriorityQueue is empty.");
        }

        /// <summary>
        /// 二分排序：快速设置最大值
        /// </summary>
        /// <param name="newIndex"></param>
        private void Sort(int newIndex)
        {
            T t = this.queue[newIndex];
            int num = newIndex / 2;
            while(newIndex > 0 && this.comparer.Compare(t, this.queue[num]) > 0)
            {
                this.queue[newIndex] = this.queue[num];
                newIndex = num;
                num /= 2;
            }
            this.queue[newIndex] = t;
        }

        private void PopSort(int index)
        {
            T t = this.queue[index];
            for(int i = index * 2; i < this.Count; i *= 2)
            {
                if (i + 1 < this.Count && this.comparer.Compare(this.queue[i + 1], this.queue[i]) > 0)
                {
                    i++;
                }
                if (this.comparer.Compare(t, this.queue[i]) >= 0)
                {
                    break;
                }
                this.queue[index] = this.queue[i];
                index = i;
            }
            this.queue[index] = t;
        }

        public IEnumerator<T> GetEnumerator()
        {
            return ((IEnumerable<T>)queue).GetEnumerator();
        }

        IEnumerator IEnumerable.GetEnumerator()
        {
            return ((IEnumerable<T>)queue).GetEnumerator();
        }
    }
}


